package com.leetcode.partition1;

import com.leetcode.common.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author `RKC`
 * @date 2021/8/20 9:27
 */
public class LC98验证二叉搜索树 {

    public static boolean isValidBST(TreeNode root) {
//        List<Integer> sequence = new ArrayList<>();
//        recursion(root, sequence);
//        for (int i = 1; i < sequence.size(); i++) {
//            if (sequence.get(i) <= sequence.get(i - 1)) return false;
//        }
//        return true;
        return iteration(root);
    }

    public static void main(String[] args) {
//        TreeNode root = new TreeNode(5, new TreeNode(4), new TreeNode(6, new TreeNode(3), new TreeNode(7)));
        TreeNode root = new TreeNode(2, new TreeNode(1), new TreeNode(3));
        System.out.println(isValidBST(root));
    }

    private static boolean iteration(TreeNode root) {
        Stack<TreeNode> s = new Stack<>();
        TreeNode cur = root;
        TreeNode pre = null;        //始终指向中序遍历当前节点的前一个节点
        while (cur != null || !s.isEmpty()) {
            if (cur != null) {
                s.push(cur);
                cur = cur.left;
                continue;
            }
            cur = s.pop();
            if (pre != null && cur.val <= pre.val) return false;
            pre = cur;
            cur = cur.right;
        }
        return true;
    }

    private static void recursion(TreeNode root, List<Integer> sequence) {
        if (root == null) return;
        recursion(root.left, sequence);
        sequence.add(root.val);
        recursion(root.right, sequence);
    }

    private static TreeNode pre = null;

    private static boolean recursion(TreeNode root) {
        if (root == null) return true;
        boolean left = recursion(root.left);
        if (pre != null && pre.val >= root.val) return false;
        pre = root;         //记录前一个节点
        boolean right = recursion(root.right);
        return left && right;
    }
}
